package com.mamingchao.basic.recursion;

import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.*;

/**
 * Created by mlamp on 2024/8/28.
 */
public class Recursion {

    public static void main(String[] args) {
        Stack<Integer> integerStack = new Stack<>();
        integerStack.push(1);
        integerStack.push(2);
        integerStack.push(9);
        integerStack.push(4);
        integerStack.push(5);

        int loop = integerStack.size();
        // 不用额外的栈，反转栈
//        int j = 0 ;
//        while ( j < loop-1){
//            reverseStack(integerStack, null, integerStack.get(j++));
//        }
//
//
//        for (int i = 0; i < loop; i++) {
//            System.out.println(integerStack.pop());
//        }

//        reverseStack2(integerStack);
//
//        for (int i = 0; i < loop; i++) {
//            System.out.println(integerStack.pop());
//        }

//        // 数字对字母的映射
//        digit2AlphMapping(105);

        // 题目7  袋子可以装的最大价值物品

//        List<Integer> weights = new LinkedList<>();
//        List<Integer> values = new LinkedList<>();

        Integer[] weights = {20, 30, 50, 55, 40};
        Integer[] values = {7, 10, 16, 5, 18};

//        weights.add(20);
//        weights.add(30);
//        weights.add(50);
//        weights.add(55);
//        weights.add(40);
//
//        values.add(7);
//        values.add(10);
//        values.add(16);
//        values.add(5);
//        values.add(18);

//        int result = maxBenefitChoice(Arrays.asList(weights), Arrays.asList(values), null ,0 , 100);
//
//        System.out.println(result);

//        int result1 = getMaxBenefit1(weights, values, 0,0  , 100);
//        int result1 = getMaxBenefit(weights, values, 0,0  , 0,100);
//
//        System.out.println(result1);

        // 题目8
//        queenIssue(new HashMap<Integer, Integer>(), 8);
        // int num = queenIssueOptimize(8);
        // System.out.println(num);

        // 题目四
//        char[] str = {'a', 'b', 'c'};
//        ArrayList<String> result = new ArrayList<>();
//        processCharCombo(str, 0 , result);
//
//        System.out.println("" + result.size());
//        for (int i = 0; i < result.size(); i++) {
//            System.out.println(result.get(i));
//        }

// 题目十一

// 8*10的象棋棋盘，马要经过K==7 步走到一个位置（5,6），问有多少总走法

    // int steps = steps(4,5,1,2,3);
    // System.out.println("总共走法：" + steps);

// 题目十二
    int[] coins = {2, 3, 5, 7};
    System.out.println(makeChange(coins,0, 10, 10));
}


    //题目四 字符串排序组合
    public static void processCharCombo(char[] str, int i, ArrayList<String> result){
        if (i == str.length) {
            result.add(String.valueOf(str));
        }

        for (int j = i; j < str.length; j++) {
            swap(str, i, j);
            processCharCombo(str, i+1, result);
            swap(str, i, j);

        }
    }




    static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    // 题目8 皇后问题

    /**
     * 题目八 皇后问题
     * 横列和纵列 都标记上index，从0 到N-1
     * 使用HashMap 存放棋牌上每行每列棋子的坐标；key为纵轴坐标，value为横轴坐标
     * @param digitLocation 每个棋子的坐标位置
     * @param N 棋盘 大小，N ==> N * N
     */
    public static boolean queenIssue(HashMap<Integer, Integer> digitLocation, int N) {

        // base case; 如果所有位置都添满了 棋子，结束
        if (digitLocation.size() >= N){
            System.out.println("本次尝试圆满结束了，尝试结果请看以上");
            System.out.println("##########################################################");
            return true;
        }
        //已经被占用的索引位置
        final int OCCUPIED = 1;
        //可用的索引位置
        final int AVAILABLE = 0;

        // 要处理的当前行的 index
        int curHangIndex = digitLocation.size();

        // 当前行 不能填写的位置，使用一个数组记录
        List<Integer> curHangDisableLieIndex = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            curHangDisableLieIndex.add(AVAILABLE);
        }

        // 如果还没放过棋子，digitLocation是空时
        if (!CollectionUtils.isEmpty(digitLocation)) {
            for(Map.Entry<Integer,Integer> item : digitLocation.entrySet()) {
                int hangIndex = item.getKey();
                int lieIndex = item.getValue();

                int gap = curHangIndex - hangIndex;
                int disableLieIndex1 = lieIndex - gap;
                int disableLieIndex2 = lieIndex + gap;

                curHangDisableLieIndex.set(lieIndex, OCCUPIED);
                if (disableLieIndex1 >= 0) {
                    curHangDisableLieIndex.set(disableLieIndex1, OCCUPIED);
                }

                if (disableLieIndex2 < N) {
                    curHangDisableLieIndex.set(disableLieIndex2, OCCUPIED);
                }
            }
        }


        if (!curHangDisableLieIndex.contains(AVAILABLE)) {
            System.out.println("该次尝试失败，该行[" + curHangIndex + "] 没有可以放的位置了;本次尝试结束了");
            System.out.println("##########################################################");
            return false;
        }

        // 在curHangIndex行，从0 到N-1的位置，除去curHangDisableLieIndex 中记录 不可用的位置，其他位置 挨个使用递归尝试
        // 在计算 可用位置和不可用位置时，使用位运算

        HashMap<Integer, Integer> digitLocationClone  = new HashMap<>();
        digitLocationClone.putAll(digitLocation);

        while (curHangDisableLieIndex.contains(AVAILABLE)) {
            int availableIndex = curHangDisableLieIndex.indexOf(AVAILABLE);
            System.out.println("该次尝试行[" + curHangIndex + "] ，放到【" + availableIndex + "】位置");
            // try this index
            curHangDisableLieIndex.set(availableIndex, OCCUPIED);
            digitLocationClone.put(curHangIndex, availableIndex);
            if (!queenIssue(digitLocationClone, N)) {
                digitLocation.remove(curHangIndex);
            }
        }

        return true;

    }

    // 皇后问题使用位运算，优化版

    /**
     * 题目八 皇后问题
     * @param n 棋盘的大小
     * @return 按照规则可以实现的摆放法最多有多少种
     */
    private static int queenIssueOptimize(int n){
        if (n <1 || n > 32) {
            return 0;
        }

        int limit = n == 32 ? -1 : (1 << n) -1;

        return queenIssueProcess(limit, 0 ,0 ,0);
    }

    /**
     * 题目八 皇后问题
     * 以 8*8 的棋盘距离说明参数含义
     * @param limit 最终列限制 (24)0|11111111
     * @param colLim  动态尝试中的列限制 (24)0|00100000
     * @param leftDialim  动态尝试中的左斜线列限制 (24)0|01000000
     * @param rightDialime  动态尝试中的右斜线列限制 (24)0|00010000
     * @return 满足规则的摆法次数
     */
    private static int queenIssueProcess(int limit, int colLim, int leftDialim, int rightDialime){

        // base case
        // 当 最终列限制 与 动态尝试中的列限制相等了，说明所有的列都已经放了元素了，已经完成了一次尝试
        if (colLim == limit) {
            return 1;
        }

        // 所有可以选择的位置
        int pos = limit & (~(colLim | leftDialim | rightDialime));

        int mostRightPositionOfPos = pos & (~pos +1);

        int res=0;
        while (mostRightPositionOfPos!=0) {
            res += queenIssueProcess(limit, colLim|mostRightPositionOfPos,
                    (leftDialim|mostRightPositionOfPos)<<1, (rightDialime|mostRightPositionOfPos)>>1);
        }


        return  res;
    }


    // 题目7 利益最大化;

    /**
     * 题目七 利益最大化;
     * 跟老师的做法一对比，这里只是一个寻常递归的一个写法，很low
     *
     * @param weights 物品重量数组；已选择的物品，重量
     * @param values 物品价值数组
     * @param alreadyWeight 已选择物品的总重量
     * @param bagCanHold 袋子可承受重量上限
     * @return 返回当前选择 + 后面可能得选择 ，所有物品的价值
     */
    public static int maxBenefitChoice(List<Integer> weights, List<Integer>  values, List<Integer> hasTried, int alreadyWeight, int bagCanHold){

        if (Objects.isNull(hasTried)){
            hasTried = new ArrayList<>();
        }

        // base case
        if (alreadyWeight >= bagCanHold || weights.size() == hasTried.size()){
            return 0;
        }

        // 最大价值
        int maxBenifit = 0;

        List<Integer> hasTriedCopy = new ArrayList<>();
        hasTriedCopy.addAll(hasTried);

        for (Integer weight : weights) {

            int tryToPutInIndex = weights.indexOf(weight);
            if (hasTriedCopy.contains(tryToPutInIndex)) {
                continue;
            }

            int curChoiceValue = values.get(tryToPutInIndex);
            hasTriedCopy.add(tryToPutInIndex);


            if (alreadyWeight + weight <= bagCanHold) {
                int curChoiceBenefit = curChoiceValue + maxBenefitChoice(weights, values, hasTriedCopy,alreadyWeight + weight, bagCanHold);
                maxBenifit = curChoiceBenefit > maxBenifit ? curChoiceBenefit : maxBenifit;
            }
        }

        // 返回当前选择 + 后面可能得选择 ，所有物品的价值
        return maxBenifit;
    }


    /**
     * 题目七 利益最大化;
     * @param weights
     * @param values
     * @param i
     * @param alreadyWeight
     * @param bagCanHold
     * @return
     */
    private static Integer getMaxBenefit1(Integer[] weights, Integer[] values, int i, int alreadyWeight, int bagCanHold) {

        // 如果已选择重量，已经达到或者超过了袋子可承受的重量，则不能再装新的物品
        if (alreadyWeight > bagCanHold){
            return -1 ;
        }

        // 如果所有的物品都已经放进袋子里，也不可再装新的物品
        if (i == weights.length) {
            return 0;
        }


        int choice1 = getMaxBenefit1(weights, values, i + 1, alreadyWeight, bagCanHold);
        int choice2 = getMaxBenefit1(weights, values, i + 1, alreadyWeight + weights[i], bagCanHold);
        choice2 = choice2 == -1 ? 0 : choice2 + values[i];

        if (choice1 >= choice2) {
            return choice1;
        } else {
            return choice2;
        }
    }

    /**
     * 题目七 利益最大化;
     * 暴力递归的方式
     * @param weights 物品重量数组；已选择的物品，重量
     * @param values 物品价值数组
     * @param i
     * @param alreadyWeight 已选择物品的总重量
     * @param bagCanHold 袋子可承受重量上限
     * @return 返回当前决定下的后续所有物品的价值
     */
    private static Integer getMaxBenefit(Integer[] weights, Integer[] values, int i, int alreadyWeight, int alreadyValue, int bagCanHold) {

        // 如果已选择重量，已经达到或者超过了袋子可承受的重量，则不能再装新的物品
        if (alreadyWeight >= bagCanHold){
            return alreadyValue ;
        }

        // 如果所有的物品都已经放进袋子里，也不可再装新的物品
        if (i >= weights.length) {
            return alreadyValue;
        }

        return Math.max(
                // 当次物品 决定不放入口袋，后续
                alreadyValue + getMaxBenefit(weights, values, i + 1, alreadyWeight, alreadyValue, bagCanHold),

                alreadyValue + getMaxBenefit(weights, values, i + 1, alreadyWeight + weights[i], values[i], bagCanHold)
        );
    }


    /**
     * 题目六
     * @param digit
     */
    public static void digit2AlphMapping(Integer digit){
        // 数字对字母的映射；index为数字，对应index存放的字母为对应的字母
        final char[] digit2AlphMapping = {' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
        String digitStr = String.valueOf(digit);
        int count = 1;
        choice(digitStr, digit2AlphMapping, count);
    }

    /**
     * 题目六
     * @param digitStr
     * @param digit2AlphMapping
     * @param count
     */
    private static void choice(String digitStr, char[] digit2AlphMapping, int count){

        // base case
        if (StringUtils.isEmpty(digitStr)) {
            System.out.println("---------------------结束----------------------------");
            return;
        }

        if (StringUtils.startsWithIgnoreCase(digitStr, "0")) {
            System.out.println("---------------------此路不通，放弃----------------------------");
            return;
        }


        System.out.println("第" + count  +  "次选择");

        // choice 1
        int firstDigit = Integer.valueOf(digitStr.substring(0,1));
        System.out.println("选择了头一个数字 --" + digit2AlphMapping[firstDigit]);
        choice(digitStr.substring(1, digitStr.length()), digit2AlphMapping, count + 1);


        // choice 2
        if (digitStr.length() > 1) {
            int firstTwoDigit = Integer.valueOf(digitStr.substring(0,2));
            if (firstTwoDigit <= 26) {
                System.out.println("第" + count +  "~次选择");
                System.out.println("选择了头两个数字 --" + digit2AlphMapping[firstTwoDigit]);
                choice(digitStr.substring(2, digitStr.length()), digit2AlphMapping, count+1);
            }
        }
    }

/**
 * 题目五 栈的逆序
 * @param ints
 */
    public static void reverseStack2(Stack<Integer> ints) {

        if (ints.isEmpty())
            return;

        int bottomElement = getBottomElement(ints);
        reverseStack2(ints);
        ints.push(bottomElement);
    }

    /**
     * 题目五 栈的逆序
     * 取 栈里面最下面的元素并返回，其他元素自动按原顺序下落
     * @param ints 原栈
     * @return 栈最底下的元素
     */
    public static int getBottomElement(Stack<Integer> ints) {

        int result = ints.pop();

        if (ints.isEmpty()) {
            return result;
        } else {
            int bottomElement = getBottomElement(ints);
            ints.push(result);
            return bottomElement;
        }
    }

    // 题目五  不用额外的数据结构，实现栈的逆序
    public static void reverseStack(Stack<Integer> ints, Integer topOne, Integer originalBottomOne){
        // 校验
        if (Objects.isNull(ints) || ints.isEmpty()){
            return;
        }

        // 如果topOne没有值，这里面从队列里面取一个值
        // 如果topOne有值，那么就沿用原来的值
        // 5
        topOne = topOne == null ?  ints.pop() : topOne;

        // base case 整个迭代任务结束
        if (topOne == originalBottomOne) {
            return;
        }

        // 4
        if (!ints.isEmpty()){
            Integer curNode = ints.pop();

            //
            if (curNode == originalBottomOne){
                ints.push(topOne);
            } else {
                reverseStack(ints,topOne,originalBottomOne);
            }
            ints.push(curNode);
        }

    }

    /**
     * 题目十一
        8*10的象棋棋盘，马要经过K==7 步走到一个位置（5,6），问有多少总走法
        N --> 象棋宽
        M --> 象棋高
        K --> 步数
        x,y 要经过K步移动到的坐标
     */
    private static int steps(int N, int M, int K, int x, int y){

        // 如果目标坐标不在棋盘内，则返回0
        if (x < 0 || x > N || y < 0 || y > M){
            return 0;
        }

        // 如果步数已经用完，则返回1
        if (K == 0){
            return 1;
        }


        // 从 x,y的位置倒推，八种可能性的累加
        return steps(N,M,K-1,x-2,y-1) +
                steps(N,M,K-1,x-2,y+1) +
                steps(N,M,K-1,x-1,y-2) +   
                steps(N,M,K-1,x-1,y+2) +
                steps(N,M,K-1,x+1,y+2) +
                steps(N,M,K-1,x+1,y-2) +
                steps(N,M,K-1,x+2,y-1) +
                steps(N,M,K-1,x+2,y+1) ;

    }

    /**
     * 题目十二 找零问题
     * 收银台 零钱类型coins 数组
     *  要找顾客的钱数- money
     * 要返回 找零的方法数
     */
    private static int makeChange(int[] coins, int coinIndex, int changeNeedToGive, int money){

        int result = 0;
        if (coins.length == 0 || changeNeedToGive < 0) {
            return 0;
        }

        if (changeNeedToGive == 0) {
            return 1;
        }


        for (int i = coinIndex; i < coins.length; i++) {
           int coin = coins[i]; 
           for (int num = 0; num * coin <= changeNeedToGive; num++) {
                changeNeedToGive = changeNeedToGive - num * coin;
                if (num ==0) {
                    coinIndex ++;
                }
                result += makeChange(coins, coinIndex, changeNeedToGive, money);
           }
        }
        return result;
    }

}
